package com.liuzhilong.infrastructure.framework.algorithms.algorithms;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * <h2>列表迭代器</h2>
 * <pre>
 *     给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
 *
 * 列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [[1,1],2,[1,1]]
 * 输出: [1,1,2,1,1]
 * 解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
 *
 * 示例 2:
 *
 * 输入: [1,[4,[6]]]
 * 输出: [1,4,6]
 * 解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。
 *
 * 通过次数33,634
 * 提交次数46,888
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-nested-list-iterator
 * </pre>
 * <p>
 *     解题思路。
 * </p>
 */
public class NestedIterator  {
    /**
     * <h2>第一中简单的方法</h2>
     * <p>
     *     思想是在一开始把所有的数据遍历到一个list里面，对外提供这个list的Iterator方法。<br>
     *      这个方法的问题是需要额外的空间存储，并且这个相当于遍历了两边数据。效率比较低下
     * </p>
     */
    public static final class Simple implements Iterator<Integer>{

        private List<Integer> data = new ArrayList<>();
        private Iterator<Integer> integerIterator = null;
        public Simple(List<NestedInteger> nestedList) {
            nestedList.forEach(this::loop);
            this.integerIterator = this.data.iterator();
        }

        //西八递归
        private void loop(NestedInteger nestedInteger){
            if (nestedInteger.isInteger()) {
                this.data.add(nestedInteger.getInteger());
            }else {
                nestedInteger.getList().forEach(this::loop);
            }
        }
        @Override
        public boolean hasNext() {
            return this.integerIterator.hasNext();
        }

        @Override
        public Integer next() {
            return this.integerIterator.next();
        }
    }

    /**
     * <h2>使用stack的方式</h2>
     * <p>
     *     思想是基于数据结构 -- 栈 进行操作。如果遍历到{@link NestedInteger#isInteger} 不是true的话，getList压入栈中进行操作。
     *     //TODO 这个不想写了。
     * </p>
     */
    public static final class ByStack implements Iterator<Integer> {
        public ByStack(List<NestedInteger> nestedList) {
        }

        @Override
        public boolean hasNext() {
            return false;
        }

        @Override
        public Integer next() {
            return null;
        }
    }


}


   interface NestedInteger {

     public boolean isInteger();

     public Integer getInteger();
     public List<NestedInteger> getList();
  }

